package demo.practice.binary_search;

public class P74 {

    public static void main(String[] args) {
        P74 p74= new P74();
        p74.searchMatrix(new int[][]{{1,3,5,7},{10,11,16,20},{23,30,34,60}},3);
    }
    //假设把二维数组平铺，那么元素总个数为matrix.length*matrix[0].length  我们叫这个数组为big
    //
    // [[1,3,5,7],          matri[0][3]  是  big[3]
    // [10,11,16,20],       matri[1][3]  是  big[3+1*matrix[0].length]
    // [23,30,34,60]]        matri[1][3] 是  big[3+2*matrix[0].length]

    //令with=matrix[0].length]  为矩形的宽度
    //则 big[n]=  matrix[n/width][n%width]


    public boolean searchMatrix(int[][] matrix, int target) {

        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return false;

        int min = 0;
        int max = matrix.length * matrix[0].length - 1;
        int width = matrix[0].length;

        while (min <=max) {
            int mid = min + (max - min) / 2;
            if (matrix[mid / width][mid % width] == target)
                return true;
            else if (matrix[mid / width][mid % width] > target) {//target在前面
                max = mid - 1;
            } else {//target在后面
                min = mid + 1;
            }
        }
        return false;
    }
}
